package com.wm.algorithm.stack;

/**
 * @ClassName: MediumStack
 * @Description: 中等级
 * @Author: Deamer
 * @Date: 2022/4/13 23:05
 **/
public class MediumStack {

    /**
     * 1541. 平衡括号字符串的最少插入次数
     * https://leetcode-cn.com/problems/minimum-insertions-to-balance-a-parentheses-string/
     * 方法: 普通计数（平衡括号串）
     * 思路：通过一个 need 变量记录对右括号的需求数，根据 need 的变化来判断是否需要插入
     *
     * @param s
     * @return
     */
    // O(n)/O(1)
    public int minInsertions(String s) {
        // res:当前总的插入次数 need:右括号的需求数
        int res = 0, need = 0;
        for (char c : s.toCharArray()) {
            if ('(' == c) {
                need += 2;
                // 当遇到左括号时，若对右括号的需求量为奇数，需要插入 1 个右括号。
                if (need % 2 == 1) {
                    // 需要插入一个右括号
                    res++;
                    // 对右括号的需求减1
                    need--;
                }
            }
            if (')' == c) {
                need--;
                // 当s=')'，我们需要让一个左括号变为"()"，但是由于一个左括号需要两个右括号，所以对右括号的需求量变为 1
                // 排除掉已经排好对的，只出现右括号)
                if (need == -1) {// 左括号少了
                    // 需要插入一个左括号
                    res++;
                    // 同时，对右括号的需求量变为1
                    need = 1;
                }
            }
        }
        return res + need;
    }

    /**
     * 921. 使括号有效的最少添加
     * https://leetcode-cn.com/problems/minimum-add-to-make-parentheses-valid/
     * 方法: 普通计数（平衡括号串）
     * 核心思路是以左括号为基准，通过维护对右括号的需求数 need，来计算最小的插入次数。
     *
     * @param s
     * @return
     */
    // O(n)/O(1) n:s字符个数/n:计数的两个变量
    public int minAddToMakeValid(String s) {
        // res:左括号的插入次数 need:记录右括号的需求数
        int res = 0, need = 0;
        for (char c : s.toCharArray()) {
            if ('(' == c) {
                need++;
            } else {
                // 对右括号的需求-1
                need--;
                if (need == -1) {// 右括号太多了，需要插入左括号
                    res++;
                    need = 0;
                }
            }
        }
        return res + need;
    }
}
